显然直接 $01$ 背包会超时并且超空间

套路：分层 $DP$

「考虑将每个子结构看作一层（也就是包含了不止 $1$ 个物品的信息），并且大层不会对小层造成影响，可以考虑先进行每一层的自我更新（即用当前层物品更新当前层答案），再进行层的合并，此时考虑低层对高层的影响」

正题

那么这题有一个特殊性质： $V_i = a \times 2^b$

b值大的物品不会影响零碎剩余的重量上限。

将物品按b值分阶段处理。

那么就是分层 $DP$

先通过普通的 $01$ 背包更新当前层自身最优解

再进行层合并：

令 $g_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$ 的最优解，$f_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$，并且再加上 $V_{total}​$ 的 $1…i - 1​$ 位的最优解

那么对于第 $i$ 层，枚举当前 $j$

对于转移，枚举在自身层内消耗的空间 $(j - k) \times 2^i$，那么还剩下 $k \times 2^i + V_{total}\{1…i - 1\}$ 的空间，分配给上一层，那么可得转移方程为

（注：$w_i$ 表示 $V_{total}$ 第 $i$ 位）
$$
f_{i, j} = \max \{g_{i, j - k} + f_{i - 1, 2k + w_i}\}
$$
同时，$g_{i, j}$ 可以通过由大到小枚举来消除

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 30 + 10;
const int MAXM = 1000 + 10;

int N, M;

LL f[MAXN][MAXM]= {0};

int getnum () {
	int num = 0;
	char ch = getchar ();
	int isneg = 0;

	while (! isdigit (ch)) {
		if (ch == '-')
			isneg = 1;
		ch = getchar ();
	}
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return isneg ? - num : num;
}

int main () {
	while (~ (N = getnum ())) {
		M = getnum ();
		memset (f, 0, sizeof (f));
		for (int i = 1; i <= N; i ++) {
			int vol = getnum (), value = getnum ();
			int b = 0;
			while (! (vol & 1))
				vol >>= 1, b ++;
			for (int j = 1000; j >= vol; j --)
				f[b][j] = max (f[b][j], f[b][j - vol] + value);
		}
		int xm = M, maxb = 0;
		while (xm)
			xm >>= 1, maxb ++;
		for (int i = 0; i <= maxb; i ++)
			for (int j = 0; j <= 1000; j ++)
				f[i][j] = max (f[i][j], f[i][j - 1]);
		LL ans = 0;
		for (int i = 1; i <= maxb; i ++)
			for (int j = min (1000, M >> i); j >= 0; j --) // 注意此处上限是 min (100, M >> i)，M >> i 保证不会将高位拿多了
				for (int k = 0; k <= j; k ++) {
					f[i][j] = max (f[i][j], f[i][j - k] + f[i - 1][min ((k << 1) + ((M >> (i - 1)) & 1), 1000)]);
					ans = max (ans, f[i][j]);
				}
		printf ("%lld\n", ans);
	}

	return 0;
}

/*
4 10
8 9
5 8
4 6
2 5
-1 -1
*/

/*
4 10
8 9
5 8
4 6
2 5
4 13
8 9
5 8
4 6
2 5
16 75594681
393216 5533
2 77
32768 467
29360128 407840
112 68
24576 372
768 60
33554432 466099
16384 318
33554432 466090
2048 111
24576 350
9216 216
12582912 174768
16384 295
1024 76
-1 -1
*/